package com.gitee.wsl.compose.chart.geometry.model.simplify


/*
 * Copyright 2012, 2013 Hannes Janetzek
 *
 * This file is part of the OpenScienceMap project (http://www.opensciencemap.org).
 *
 * This program is free software: you can redistribute it and/or modify it under the
 * terms of the GNU Lesser General Public License as published by the Free Software
 * Foundation, either version 3 of the License, or (at your option) any later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT ANY
 * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A
 * PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
 *
 * You should have received a copy of the GNU Lesser General Public License along with
 * this program. If not, see <http://www.gnu.org/licenses/>.
 */

import com.gitee.wsl.compose.chart.geometry.model.GeometryBuffer
import com.gitee.wsl.compose.chart.geometry.model.GeometryUtils
import com.gitee.wsl.compose.chart.geometry.model.pool.Inlist
import com.gitee.wsl.compose.chart.geometry.model.pool.Pool
import com.gitee.wsl.ext.base.Arrays.arraycopy
import kotlin.math.abs

/**
 * Visvalingam-Wyatt simplification
 *
 * based on:
 * https://github.com/mbloch/mapshaper/blob/master/src/mapshaper-visvalingam.js
 */
class SimplifyVW {
    inner class Item : Inlist<Item>() {
        var index = 0
        var id = 0
        var area = 0f
        var prev: Item? = null
    }

    var pool: Pool<Item> = object : Pool<Item>() {
        override fun createItem(): Item {
            return Item()
        }
    }
    private var heap = arrayOfNulls<Item>(100)
    private var size = 0
    fun simplify(geom: GeometryBuffer, minArea: Float) {
        var prev: Item? = null
        var first: Item? = null
        var item: Item?
        size = 0
        if (heap.size < geom.pointPos shr 1) heap = arrayOfNulls(geom.pointPos shr 1)
        prev = push(0, Float.MAX_VALUE)
        first = prev
        var i = 2
        while (i < geom.pointPos - 2) {
            item = push(i, area(geom.points, i - 2, i, i + 2))
            prev!!.next = item
            item.prev = prev
            prev = item
            i += 2
        }
        val last = push(geom.pointPos - 2, Float.MAX_VALUE)

        //		sorter.doSort(heap, DistanceComparator, 0, size);
        //		for (int i = 0; i < size; i++)
        //			heap[i].index = i;
        last.prev = prev
        prev!!.next = last
        last.next = first
        first.prev = last
        while (pop().also { item = it } != null) {
            if (item!!.area > minArea) break
            if (item!!.prev === item!!.next) break
            item!!.prev!!.next = item!!.next
            item!!.next!!.prev = item!!.prev
            if (item!!.prev !== first) update(geom, item!!.prev)
            if (item!!.next !== first) update(geom, item!!.next)
            item = pool.release(item!!)
        }
        first.prev!!.next = null
        first.prev = null
        item = first
        val points = FloatArray(geom.pointPos)
        arraycopy(geom.points, 0, points, 0, geom.pointPos)
        geom.clear()
        geom.startPolygon()
        while (item != null) {
            val x = points[item!!.id]
            val y = points[item!!.id + 1]
            geom.addPoint(x, y)
            item = item!!.next
        }
        first = pool.release(first)
    }

    private fun update(geom: GeometryBuffer, it: Item?) {
        val area = area(geom.points, it!!.prev!!.id, it.id, it.next!!.id)
        update(it, area)
        //remove(it);
        //it.area = area(geom.points, it.prev.id, it.id, it.next.id);
        //push(it);
    }

    fun push(it: Item) {
        heap[size] = it
        it.index = size
        up(size++)
    }

    fun push(id: Int, area: Float): Item {
        val it: Item = pool.get()
        heap[size] = it
        it.index = size
        it.area = area
        it.id = id
        up(size++)
        return it
    }

    fun pop(): Item? {
        if (size == 0) return null
        val removed = heap[0]
        val obj = heap[--size]
        heap[size] = null
        if (size > 0) {
            heap[0.also { obj!!.index = it }] = obj
            down(0)
        }
        return removed
    }

    fun update(it: Item?, area: Float) {
        if (area < it!!.area) {
            it.area = area
            up(it.index)
        } else {
            it.area = area
            down(it.index)
        }
    }

    fun remove(removed: Item): Int {
        check(size != 0) { "size == 0" }
        val i = removed.index
        val obj = heap[--size]
        heap[size] = null

        /* if min obj was popped */if (i == size) return i

        /* else put min obj in place of the removed item */obj!!.index = i
        heap[i] = obj
        if (obj.area < removed.area) {
            up(i)
        } else down(i)
        return i
    }

    private fun up(i: Int) {
        var i = i
        val it = heap[i]
        while (i > 0) {
            val up = (i + 1 shr 1) - 1
            val parent = heap[up]
            if (it!!.area >= parent!!.area) break
            parent.index = i
            heap[i] = parent
            i = up
            it.index = i
            heap[i] = it
        }
    }

    private fun down(i: Int) {
        var i = i
        val item = heap[i]
        while (true) {
            val right = i + 1 shl 1
            val left = right - 1
            var down = i
            var child = heap[down]
            if (left < size && heap[left]!!.area < child!!.area) child = heap[left.also {
                down = it
            }]
            if (right < size && heap[right]!!.area < child!!.area) child = heap[right.also {
                down = it
            }]
            if (down == i) break
            heap[i.also { child!!.index = it }] = child
            heap[down.also { i = it }.also { item?.index = it }] = item
        }
    }

    companion object {
        fun area(a: FloatArray, p1: Int, p2: Int, p3: Int): Float {
            val area = GeometryUtils.area(a, p1, p2, p3)
            var dotp = GeometryUtils.dotProduct(a, p1, p2, p3)
            //return (float) (area * (0.5 + 0.5 * (1 - dotp * dotp)));
            dotp = abs(dotp)
            val weight = if (dotp < 0.5) 0.1 else if (dotp < 1) 0.3 else 1
            return area * weight.toFloat()
        }
    }
}

